package com.demo.java.OD601_650.OD622;

import java.util.*;
import java.util.stream.Collectors;

/**
 * @author bug菌
 * @Source 公众号：猿圈奇妙屋
 * @des： 【探索地块建立(A卷-100分)】问题
 * @url： https://blog.csdn.net/weixin_43970743/article/details/146883943
 */
public class OdMain {
    public static void main(String[] args) {
        // 处理输入
        Scanner in = new Scanner(System.in);
        // 解析输入，n为行数，m为列数，c为子矩阵边长，k为阈值
        List<Integer> params = Arrays.stream(in.nextLine().split(" "))
                .map(Integer::parseInt)
                .collect(Collectors.toList());
        int n = params.get(0);
        int m = params.get(1);
        int c = params.get(2);
        int k = params.get(3);

        // 初始化输入矩阵
        int[][] matrix = new int[n][m];
        for (int i = 0; i < n; i++) {
            String[] num_strs = in.nextLine().split(" ");
            for (int j = 0; j < m; j++) {
                matrix[i][j] = Integer.parseInt(num_strs[j]);
            }
        }

        // 输出符合条件的子矩阵数量
        System.out.println(get_area_count(matrix, k, c));
    }

    // 计算符合条件的子矩阵的数量
    public static int get_area_count(int[][] mat, int threshold, int c) {
        int n = mat.length;
        int m = mat[0].length;

        // 初始化前缀和矩阵，大小为(n+1)*(m+1)，方便计算边界
        int[][] s = new int[n + 1][m + 1];

        // 生成前缀和子矩阵，s[i][j]表示从(0,0)到(i-1,j-1)的矩阵和
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= m; ++j) {
                s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + mat[i - 1][j - 1];
            }
        }

        int ans = 0;
        // 遍历所有可能的边长为c的子矩阵
        for (int i = c; i <= n; ++i) {
            for (int j = c; j <= m; ++j) {
                // 计算当前c*c子矩阵的和，s[i][j] - s[i-c][j] - s[i][j-c] + s[i-c][j-c]
                int sum = s[i][j] - s[i - c][j] - s[i][j - c] + s[i - c][j - c];
                // 如果该子矩阵的和大于等于阈值threshold，则计数
                if (sum >= threshold) {
                    ans++;
                }
            }
        }

        // 返回符合条件的子矩阵数量
        return ans;
    }
}